package com.sheng.leetcode.year2022.swordfingeroffer.day14;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 剑指 Offer 12. 矩阵中的路径<p>
 *<p>
 * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。<p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。<p>
 * 例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。<p>
 *<p>
 * 示例 1：<p>
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"<p>
 * 输出：true<p>
 *<p>
 * 示例 2：<p>
 * 输入：board = [["a","b"],["c","d"]], word = "abcd"<p>
 * 输出：false<p>
 *<p>
 * 提示：<p>
 *<p>
 * m == board.length<p>
 * n = board[i].length<p>
 * 1 <= m, n <= 6<p>
 * 1 <= word.length <= 15<p>
 * board 和 word 仅由大小写英文字母组成<p>
 * 注意：本题与主站 79 题相同：<a href="https://leetcode-cn.com/problems/word-search/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0012 {

    @Test
    public void test01() {
//        char[][] board = {
//                {'A','B','C','E'},
//                {'S','F','C','S'},
//                {'A','D','E','E'}
//        };
//        String word = "ABCCED";

        char[][] board = {
                {'a','b'},
                {'c','d'}
        };
        String word = "abcd";
        System.out.println(new Solution().exist(board, word));
    }
}
class Solution {
    boolean flag = false;
    int m;
    int n;
    char[][] chars;
    String s;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        chars = board;
        s = word;
        // 该数组用来存储当前路径下的单词是否使用过，0代表没使用，1代表使用过
        int[][] ints = new int[m][n];
        // 给二维数组赋初始值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ints[i][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从矩阵中任选一点作为起始点出发
                ergodic(ints, i, j, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return flag;
    }

    public void ergodic(int[][] ints, int i, int j, int cur) {
        // 单词已经遍历完
        if (cur == s.length()) {
            flag = true;
            return;
        }
        // 越界
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        // 当前位置已被使用
        if (ints[i][j] == 1) {
            return;
        }
        // 字符不相等
        if (chars[i][j] != s.charAt(cur)) {
            return;
        }
        // 改为已使用
        ints[i][j] = 1;
        // 对上下左右继续进行寻找
        ergodic(ints, i - 1, j, cur + 1);
        ergodic(ints, i + 1, j, cur + 1);
        ergodic(ints, i, j - 1, cur + 1);
        ergodic(ints, i, j + 1, cur + 1);
        // 除去已使用
        ints[i][j] = 0;
    }
}

//https://www.cnblogs.com/yxygrqlx/articles/13299824.html
//public class Solution {
//    private boolean flag;
//    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
//    {
//        for(int i=0;i<rows;i++){
//            for(int j=0;j<cols;j++){
//                if(matrix[i*cols+j]==str[0]){
//                    boolean[][]state=new boolean[rows][cols];
//                    dfs(matrix,rows,cols,str,state,i,j,0);
//                    if(flag)
//                        return true;
//                }
//            }
//        }
//        return false;
//    }
//   void dfs(char[]matrix,int rows,int cols,char[]str,boolean[][]state,int i,int j,int cur){
//        if(cur==str.length){
//            flag=true;
//            return ;
//        }
//        if(flag)
//            return ;
//        if(i<0||i>=rows||j<0||j>=cols)
//            return ;
//        if(state[i][j])
//            return ;
//        if(matrix[i*cols+j]!=str[cur])
//            return ;
//        state[i][j]=true;
//        dfs(matrix,rows,cols,str,state,i-1,j,cur+1);
//        dfs(matrix,rows,cols,str,state,i+1,j,cur+1);
//        dfs(matrix,rows,cols,str,state,i,j-1,cur+1);
//        dfs(matrix,rows,cols,str,state,i,j+1,cur+1);
// /// 注意回溯
//        state[i][j]=false;
//        cur--;
//    }
//}
